/**
 * 
 */
package cn.edu.cqu.bysj.wm.keynode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

import org.neo4j.graphdb.Node;

import cn.edu.cqu.bysj.wm.util.MapComparator2;

/**
 * @author Meng
 * 
 */
public class Fagin {

	public List<Node> keyNodes;

	Map<Integer, Double> nodeScore;
	Map<Long, Integer> map;
	double[][] record;
	int count;
	int n;

	static int[] flag;

	/**
	 * process of fagin search,gain the top-k key nodes
	 * 
	 * @param cTool
	 * @param k
	 */
	public void FA(CentralityTool cTool, int k) {
		flag = cTool.flag;
		keyNodes = new ArrayList<Node>();
		nodeScore = new LinkedHashMap<Integer, Double>();
		map = new HashMap<Long, Integer>();

		n = cTool.nodes.size();
		count = 0;

		// init record matrix
		record = new double[n][6];
		for (int i = 0; i < n; i++) {
			map.put(cTool.nodes.get(i).getId(), i);
			for (int j = 0; j < 6; j++) {
				if (flag[j] == 1) {
					record[i][j] = -100;
				}
			}
		}

		normalize(cTool.rankValue);

		// sorted access
		for (int i = 0; i < n; i++) {

			// judge to stop sorted access
			if (!sortedStop(k)) {
				for (int j = 0; j < 6; j++) {
					if (flag[j] == 1) {
						// get the node id
						long id = cTool.rankNode[i][j];
						// find postion in record
						int recordPos = map.get(id);
						// record the value of index j
						record[recordPos][j] = cTool.rankValue[i][j];

						if (nodeScore.containsKey(recordPos)) {
							nodeScore.put(recordPos, nodeScore.get(recordPos)
									+ record[recordPos][j]);
						} else {
							nodeScore.put(recordPos, record[recordPos][j]);
						}
					}
				}
			}
		}

		/**
		 * random access
		 */
		for (int i : nodeScore.keySet()) {
			for (int j = 0; j < 6; j++) {
				if (record[i][j] == -100 && flag[j] == 1) {
					int pos = cTool.rank[i][j];
					record[i][j] = cTool.rankValue[pos][j];
					nodeScore.put(i, nodeScore.get(i) + record[i][j]);
				}
			}
		}

		/**
		 * rank and gain the top-k nodes
		 */
		List<Map.Entry<Integer, Double>> list = new ArrayList<Map.Entry<Integer, Double>>(
				nodeScore.entrySet());
		Collections.sort(list, new MapComparator2());
		int i = 0;
		for (Map.Entry<Integer, Double> entry : list) {
			if (i >= k) {
				break;
			}
			keyNodes.add(cTool.nodes.get(entry.getKey()));
			i++;
		}
	}

	/**
	 * judge whether sorted accesee can stop
	 * 
	 * @param k
	 *            top-k
	 * @return true of false
	 */
	public boolean sortedStop(int k) {
		for (int i : nodeScore.keySet()) {
			for (int j = 0; j < 6; j++) {
				if (record[i][j] == -100 && flag[j] == 1) {
					return false;
				}
			}
			count++;
			if (count == k) {// already found k nodes with completed infos of
								// all the index
				return true;
			}
		}
		return false;
	}

	/**
	 * normalize of rankValue[][]
	 * 
	 * @param rankValue
	 */
	private void normalize(double[][] rankValue) {

		double[] mean = new double[6];
		double[] std = new double[6];

		for (int i = 0; i < 6; i++) {
			mean[i] = 0;
			std[i] = 0;
		}

		// calculate average
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 6; j++) {
				if (flag[j] == 1) {
					mean[j] = mean[j] + rankValue[i][j];
				}
			}
		}
		for (int j = 0; j < 6; j++) {
			if (flag[j] == 1) {
				mean[j] = mean[j] / n;
			}
		}
		// calculate standard deviation
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 6; j++) {
				if (flag[j] == 1) {
					std[j] = (rankValue[i][j] - mean[j])
							* (rankValue[i][j] - mean[j]) + std[j];
				}
			}
		}
		for (int j = 0; j < 6; j++) {
			if (flag[j] == 1) {
				std[j] = Math.sqrt(std[j]);
			}
		}
		// Gauss normalization
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 6; j++) {
				if (flag[j] == 1) {
					rankValue[i][j] = (rankValue[i][j] - mean[j]) / std[j];
				}
			}
		}

	}
}
